509. 斐波那契数
509. 斐波那契数
Similar Question
Solution Tips
方案一: 递归
直接按照定义
计算 fib(n - 1) 和 fib(n -2) 有很多重复的计算, 所以时间复杂度就会高很多
这也是递归转动态规划的一个常见的重要原因, 记忆化搜索
var fibonacci = function(n) {
// 一题多种视角
// 递归视角
if (n === 0) return 0;
if (n === 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
};
方法二: 动态规划
这里我们要用一个一维 dp 数组来保存递归的结果
确定 Dp 数组以及下标的含义
dp[i] 的定义为：第 i 个数的斐波那契数值是 dp[i]
确定递推公式
为什么这是一道非常简单的入门题目呢？
因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
Dp 数组如何初始化
题目中把如何初始化也直接给我们了，如下：
dp[0] = 0
dp[1] = 1
确定遍历顺序
从递归公式 dp[i] = dp[i - 1] + dp[i - 2] 中可以看出，dp[i] 是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
举例推导 Dp 数组
按照这个递推公式 dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当 N 为 10 的时候，dp 数组应该是如下的数列：
0 1 1 2 3 5 8 13 21 34 55
如果代码写出来，发现结果不对，就把 dp 数组打印出来看看和我们推导的数列是不是一致的。
var fib = function(n) {
let dp = [0, 1]
for(let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
console.log(dp)
return dp[n]
};
当然可以发现，我们只需要维护两个数值就可以了，不需要记录整个序列。
var fib = function(n) {
// 动规状态转移中，当前结果只依赖前两个元素的结果，所以只要两个变量代替dp数组记录状态过程。将空间复杂度降到O(1)
let pre1 = 1
let pre2 = 0
let temp
if (n === 0) return 0
if (n === 1) return 1
for(let i = 2; i <= n; i++) {
temp = pre1
pre1 = pre1 + pre2
pre2 = temp
}
return pre1
};